// https://leetcode.cn/problems/linked-list-cycle/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 快慢指针法判断链表是否有环
// 2. 慢指针每次走一步，快指针每次走两步
// 3. 如果链表有环，快慢指针必定会相遇
// 4. 如果快指针遇到nullptr，说明链表无环
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include "LinkedListUtils.h"

class Solution 
{
public:
    bool hasCycle(ListNode* head) 
    {
        ListNode* slow = head, *fast = head;

        while (fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;

            if (fast == slow)
            {
                return true;
            }
        }

        return false;
    }
};

int main()
{
    vector<int> nums1 = {3,2,0,-4}, nums2 = {1,2};
    Solution sol;

    auto l1 = createLinkedList(nums1);
    l1->next->next->next->next = l1->next;

    auto l2 = createLinkedList(nums2);
    l2->next->next = l2;

    cout << (sol.hasCycle(l1) == true ? "True" : "False") << endl;
    cout << (sol.hasCycle(l2) == true ? "True" : "False") << endl;

    return 0;
}